// write your code here
import java.util.*;
public class Main{
    public static void main(String[] args) {
        int[] arr = new int[10001];
        arr[1] = 1;
        arr[2] = 2;
        for(int i = 3;i<=10000;i++) {
            arr[i] = (arr[i-1] + arr[i-2])%10000;
        }
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()) {
            int n = scanner.nextInt();
            for(int i = 1;i<=n;i++) {
                int count = scanner.nextInt();
               System.out.printf("%04d",arr[count]);
            }
            System.out.println();
        }
        
        
    }
}